package com.wyw.learning.offer;

import java.util.*;

/**
 * 从上到下打印二叉树
 *      1、从上到下打印出二叉树的没换个节点，同一层的节点按照从左到右打印
 *
 * @Author Mr Wu yewen.wu.china@gmail.com
 * @Date 2023/2/21 9:48
 */
public class Offer032 {

    public static void main(String[] args) {
        TreeNode root = new TreeNode(0);
        TreeNode treeNode1 = new TreeNode(1);
        TreeNode treeNode2 = new TreeNode(2);
        TreeNode treeNode3 = new TreeNode(3);
        TreeNode treeNode4 = new TreeNode(4);
        TreeNode treeNode5 = new TreeNode(5);
        TreeNode treeNode6 = new TreeNode(6);
        TreeNode treeNode7 = new TreeNode(7);
        TreeNode treeNode8 = new TreeNode(8);
        TreeNode treeNode9 = new TreeNode(9);
        TreeNode treeNode10 = new TreeNode(10);
        root.left=treeNode1;
        root.right=treeNode2;
        treeNode1.left=treeNode3;
        treeNode1.right=treeNode4;
        treeNode2.left=treeNode5;
        treeNode2.right=treeNode6;
        treeNode3.right=treeNode7;
        treeNode7.left=treeNode10;
        treeNode4.left=treeNode8;
        treeNode4.right=treeNode9;

//        levelOrder(root);
//        levelOrder2(root);
        levelOrder3(root);
    }

    /**
     * 广度优先
     * 1、特例处理： 当树的根节点为空，则直接返回空列表 [] ；
     * 2、初始化： 打印结果列表 res = [] ，包含根节点的队列 queue = [root] ；
     * 3、BFS 循环： 当队列 queue 为空时跳出；
     *      出队： 队首元素出队，记为 node；
     *      打印： 将 node.val 添加至列表 tmp 尾部；
     *      添加子节点： 若 node 的左（右）子节点不为空，则将左（右）子节点加入队列 queue ；
     * 4、返回值： 返回打印结果列表 res 即可。
     *
     * @param root
     * @return
     */
    public static int[] levelOrder(TreeNode root) {
        if(root == null) return new int[0];
        Queue<TreeNode> queue = new LinkedList<TreeNode>(){{ add(root); }};
        ArrayList<Integer> ans = new ArrayList<>();
        while(!queue.isEmpty()) {
            TreeNode node = queue.poll();
            ans.add(node.val);
            if(node.left != null) queue.add(node.left);
            if(node.right != null) queue.add(node.right);
        }
        int[] res = new int[ans.size()];
        for(int i = 0; i < ans.size(); i++)
            res[i] = ans.get(i);
        return res;
    }

    /**
     * 从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行
     * @param root
     * @return
     */
    public static List<List<Integer>> levelOrder2(TreeNode root) {
        List<List<Integer>> ret = new ArrayList<>();
        if (root == null) {
            return ret;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            List<Integer> level = new ArrayList<>();
            int currentLevelSize = queue.size();
            for (int i = 1; i <= currentLevelSize; ++i) {
                TreeNode node = queue.poll();
                level.add(node.val);
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            ret.add(level);
        }

        return ret;

    }

    static List<List<Integer>> node=new ArrayList();

    public static List<List<Integer>> levelOrder21(TreeNode root) {
        helper(root,0);
        return node;
    }

    public static void helper(TreeNode root, int k){
        if(root!=null){
            if(node.size()<=k)node.add(new ArrayList());
            node.get(k).add(root.val);
            helper(root.left,k+1);
            helper(root.right,k+1);
        }
    }


    /**
     * 请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，
     * 第二层按照从右到左的顺序打印，
     * 第三行再按照从左到右的顺序打印，其他行以此类推。
     * @param root
     * @return
     */
    public static List<List<Integer>> levelOrder3(TreeNode root) {
        List<List<Integer>> ret = new ArrayList<>();
        if (root == null) {
            return ret;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int currentLevelNum = 1;
        while (!queue.isEmpty()) {
            List<Integer> level = new ArrayList<>();
            int currentLevelSize = queue.size();
            for (int i = 1; i <= currentLevelSize; ++i) {
                TreeNode node = queue.poll();
                level.add(node.val);
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            if(currentLevelNum % 2 == 0) {
                Collections.reverse(level);
            }

            ret.add(level);
            currentLevelNum ++;
        }

        return ret;

    }

    public static List<List<Integer>> levelOrder31(TreeNode root) {
        List<List<Integer>> ans = new LinkedList<>();
        if (root == null) {
            return ans;
        }

        Queue<TreeNode> nodeQueue = new ArrayDeque<>();
        nodeQueue.offer(root);
        boolean isOrderLeft = true;

        while (!nodeQueue.isEmpty()) {
            Deque<Integer> levelList = new LinkedList<>();
            int size = nodeQueue.size();
            for (int i = 0; i < size; ++i) {
                TreeNode curNode = nodeQueue.poll();
                if (isOrderLeft) {
                    levelList.offerLast(curNode.val);
                } else {
                    levelList.offerFirst(curNode.val);
                }
                if (curNode.left != null) {
                    nodeQueue.offer(curNode.left);
                }
                if (curNode.right != null) {
                    nodeQueue.offer(curNode.right);
                }
            }
            ans.add(new LinkedList<>(levelList));
            isOrderLeft = !isOrderLeft;
        }

        return ans;

    }


    static List<List<Integer>> res=new ArrayList<>();
    public static List<List<Integer>> levelOrder32(TreeNode root) {

        helper1(root, 0);
        return res;

    }

    private static void helper1(TreeNode root, int level){
        if(root==null)
            return;
        if(res.size()==level){
            res.add(new ArrayList<>());
        }
        if(level%2==0){
            res.get(level).add(root.val);

        }else{
            res.get(level).add(0,root.val);
        }
        helper1(root.left,level+1);
        helper1(root.right,level+1);

    }


}


